package 算法.练习1;
import java.util.*;

/**
 * @author:谢君臣
 * @Date:2021/9/4-22:27
 * @version:1.0
 * @function:
 */
public class LRU {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        LRUNode lruNode = new LRUNode(k);
        List<Integer> res = new ArrayList<>();
        for (int[] operator : operators) {
            if (operator[0]==1){
                String key = String.valueOf(operator[1]);
                int value = operator[2];
                lruNode.put(key,value);
            }else if (operator[0]==2){
                String key = String.valueOf(operator[1]);
                int value = lruNode.get(key);
                res.add(value);
            }else {
                System.out.println("异常输入");
            }
        }
        int[]r = new int[res.size()];
        Iterator<Integer> iterator = res.iterator();
        int i =0;
        while (iterator.hasNext()){
            r[i++] = iterator.next();
        }
        return r;
    }
    class LRUNode{
        public void put(String key, int value) {
            Node node = new Node(key,value);
            this.keyMap.put(key,node);
            if (this.head==null){ // 初始化
                this.head = node;
                this.tail = this.head;
            }else {
                // 先放入
                tail.next = node;
                node.pre = tail;
                tail = node;
                checkSize(); // 再判断
            }
        }

        private void checkSize() {
            if (this.keyMap.size()>this.capacity){
                this.keyMap.remove(this.head.key);
                this.head.next.pre = null;
                this.head = this.head.next;
            }
        }

        public int get(String key) {
            if (this.keyMap.containsKey(key)){
                Node node = this.keyMap.get(key);
                int value = node.value;
                if (node==head){
                    put(node.key,node.value);
                    this.head.next.pre = null;
                    this.head = this.head.next;
                }else if (node==tail){
                    //
                }else {
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                    node.next = null;
                    node.pre = null;
                    put(node.key,node.value);
                }
                return value;
            }
            else return -1;
        }


        private final int capacity;
        private final HashMap<String, Node> keyMap;
        private Node head; // 头节点
        private Node tail;  // 尾节点

        public LRUNode() {
            this.capacity = 10;
            this.head = null;
            this.tail = null;
            this.keyMap = new HashMap();
        }

        public LRUNode(int capacity) {
            this.capacity = capacity;
            this.head = null;
            this.tail = null;
            this.keyMap = new HashMap();
        }
    }
    class Node{
        private final String key;
        private final int value;
        private Node next;
        private Node pre;

        public Node(String key,int value) {
            this.key = key;
            this.value = value;
            this.next = null;
            this.pre = null;
        }
        public Node(String key,int value, Node next, Node pre) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.pre = pre;
        }
    }
}
